πŸ‘©β€πŸ’» 72412. μˆœμœ„ 검색

@Seongukbaek Posted July 01, 2022 Β· Updated July 01, 2022 Β· 3 min read

문제

Programmers - μˆœμœ„ 검색

πŸ“ Logic

// -λ₯Ό λΆ™μ΄λ©΄μ„œ κ°€λŠ₯ν•œ 쑰합을 μƒμ„±ν•˜μ—¬ map에 μΆ”κ°€ν•œλ‹€. private static void makeComb(int length) { if (length == 4) { String key = String.join("", combStr); scoreMap.putIfAbsent(key, new ArrayList<>()); scoreMap.get(key).add(infoScore); } else { // -κ°€ μ•„λ‹Œ κ²½μš°μ™€ -인 경우둜 λ‚˜λˆ  κ°€λŠ₯ν•œ μ‘°ν•© 생성 combStr[length] = infoLine[length]; makeComb(length + 1); combStr[length] = "-"; makeComb(length + 1); } }
  • -λ₯Ό λΆ™μ΄λ©΄μ„œ κ°€λŠ₯ν•œ 정보λ₯Ό λ§Œλ“œλŠ” ν•¨μˆ˜
  • DFS λ°©μ‹μœΌλ‘œ 기쑴의 정보λ₯Ό μ‚¬μš©ν•˜κ±°λ‚˜, -λ₯Ό λΆ™μ΄κ±°λ‚˜ ν•˜μ—¬ μƒμ„±ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { // μ–Έμ–΄, 직ꡰ, κ²½λ ₯, μ†ŒμšΈν‘Έλ“œλ₯Ό key둜 κ°€μ§€κ³ , 점수 리슀트λ₯Ό κ°’μœΌλ‘œ κ°€μ§€λŠ” map μ„ μ–Έ static Map<String, ArrayList<Integer>> scoreMap = new HashMap<>(); // μ‘°ν•© 생성을 μœ„ν•΄ μ‚¬μš©ν•  λ°°μ—΄, μ½”ν…Œ 점수, μ§€μ›μžμ˜ 정보 λ°°μ—΄ static String[] combStr; static int infoScore; static String[] infoLine; public int[] solution(String[] info, String[] query) { int[] answer = new int[query.length]; // μ£Όμ–΄μ§„ info 배열을 κ°€μ§€κ³  scoreMap μ΄ˆκΈ°ν™” // -λ₯Ό ν¬ν•¨ν•œ λͺ¨λ“  쑰합을 μƒμ„±ν•˜μ—¬ map의 key둜 μΆ”κ°€ initScoreMap(info); // 이진탐색을 μœ„ν•΄ 점수 리슀트λ₯Ό μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬ for (String key : scoreMap.keySet()) Collections.sort(scoreMap.get(key)); for (int i = 0; i < query.length; i++) { String[] line = query[i].split(" and | "); StringBuilder sb = new StringBuilder(line[0] + line[1] + line[2] + line[3]); String key = sb.toString(); int score = Integer.parseInt(line[4]); if (scoreMap.containsKey(key)) { ArrayList<Integer> list = scoreMap.get(key); answer[i] = list.size() - findLower(list, score); } } return answer; } private static void initScoreMap(String[] info) { for (String i : info) { combStr = new String[4]; infoLine = i.split(" "); infoScore = Integer.parseInt(infoLine[4]); makeComb(0); } } // -λ₯Ό λΆ™μ΄λ©΄μ„œ κ°€λŠ₯ν•œ 쑰합을 μƒμ„±ν•˜μ—¬ map에 μΆ”κ°€ν•œλ‹€. private static void makeComb(int length) { if (length == 4) { String key = String.join("", combStr); scoreMap.putIfAbsent(key, new ArrayList<>()); scoreMap.get(key).add(infoScore); } else { // -κ°€ μ•„λ‹Œ κ²½μš°μ™€ -인 경우둜 λ‚˜λˆ  κ°€λŠ₯ν•œ μ‘°ν•© 생성 combStr[length] = infoLine[length]; makeComb(length + 1); combStr[length] = "-"; makeComb(length + 1); } } private static int findLower(ArrayList<Integer> list, int value) { int left = 0; int right = list.size() - 1; while (left <= right) { int mid = (left + right) / 2; int v = list.get(mid); if (v < value) left = mid + 1; else right = mid - 1; } return left; } }

✏️ Review

  • -κ°€ ν¬ν•¨λœ 경우λ₯Ό μœ„ν•΄ κ°€λŠ₯ν•œ λͺ¨λ“  정보λ₯Ό λ§Œλ“€μ–΄λ‘κ³  이λ₯Ό μ‚¬μš©ν•˜λŠ” 아이디어λ₯Ό μ‚¬μš©ν–ˆλ‹€.
  • 이진 탐색을 μ‚¬μš©ν•΄ λΉ λ₯΄κ²Œ 인원을 κ΅¬ν•˜λŠ” 아이디어가 μ£Όμš”ν–ˆλ˜ 것 κ°™λ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€